package com.yinxin.wudasuanfa.dongtaiguihua;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 回溯算法:八皇后问题
 *  8*8 棋盘,皇后棋子放在棋盘上，不允许两个皇后棋子会出现在一条直线或者斜线上
 *  算法思路：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
 */
public class Exercise4 {
    static int count = 0;//记录有⼏种⽅法
    int max = 8;//max表⽰⼏个皇后
    int[] arr = new int[max];//⽤⼀个数组表⽰，其中arr[n]表⽰放在第arr[n]+1列，n表⽰第n+1个皇后，放在第n+1⾏

    public static void main(String[] args) {
        Exercise4 queen = new Exercise4();
        queen.store(0);
        System.out.printf("⼀共有%d种放置⽅法", count);
    }

    //在棋盘上放置第⼏个皇后
    private void store(int n) {
        if (n == 8) { //如果所有皇后放置完毕，则输出
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[n] = i;
            if (Judg(n)) {  //判断是否与前⾯放置的有冲突
                store(n + 1);
            }
        }
    }

    private boolean Judg(int n) {
        for (int i = 0; i < n; i++) {
            //arr[i] == arr[n] 表⽰是否在同⼀列
            //Math.abs(n - i) == Math.abs(arr[n] - arr[i]) 表⽰是否在同⼀斜线
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    //⽤于显⽰⼋皇后的位置
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + 1 + " ");
        }
        System.out.println();
    }

}
